
/// 针对具有大量数据的查询时,高效进行 插入、删除、搜索以及清理的操作设计的稀疏集存储数据结构
#[derive(Debug,Clone,Default)]
pub(crate) struct SparseSet<T> {
    /// 存储实际的数据元素
    dense:Vec<T>,
    /// 存储实际数据元素的位置索引
    sparse:Vec<Option<usize>>,
    /// 实际数据的索引对应的 索引列表中的索引
    dense_index_into_sparse_index:Vec<usize>
}

impl<T> SparseSet<T> {
    pub(crate) fn insert(&mut self, index:usize,data:T) {
        if self.sparse.len() <= index {
            self.sparse.resize(index + 1, None);
        }

        let new_index = self.dense.len();
        self.sparse[index] = Some(new_index);
        self.dense.push(data);
        self.dense_index_into_sparse_index.push(index);
    }

    pub fn get(&self, index:usize) -> Option<&T> {
        Some(&self.dense[(*self.sparse.get(index)?)?])
    }

    pub fn len(&self) -> usize {
        self.dense.len()
    }

    pub fn dense(&self) -> &[T] {
        &self.dense
    }

    pub fn dense_index_into_sparse_index(&self) -> &[usize] { &self.dense_index_into_sparse_index }
}   




mod test {
    use super::SparseSet;

    #[test]
    fn test_sparse_set() {
        let mut sparse_set = SparseSet::default();

        sparse_set.insert(10, 1);
        sparse_set.insert(2, 99);

        assert!(sparse_set.len() == 2);
        assert!(sparse_set.get(10) == Some(&1));

    }
}







